package com.jhy.suixianglu.daima20230111;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 之前因为元旦放假和自己毕业设计和学习spring耽误了时间
 * 现在开始2023年的算法学习生活
 */
public class ThreeSum2 {
    public List<List<Integer>> threeSum(int[] nums) {
        // 首先我们收集一个结果集
        ArrayList<List<Integer>> res = new ArrayList<>();
        // 然后对我们的数组进行排序 方便我们后面指针的操作
        Arrays.sort(nums);
        for (int i = 0; i <= nums.length - 1; i++) {
            // 进行剪枝的操作
            if (nums[i] > 0) {
                return res;
            }
            // 进行a的元素的去重操作
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 定义两个指针的操作
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                // 进行双指针的判断了
                int target = nums[i] + nums[left] + nums[right];
                if (target > 0) {
                    right--;
                } else if (target < 0) {
                    left++;
                } else {
                    // 先加入到结果集当中
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    // 继续对b,c进行去重的操作
                    while(left<right && nums[left] == nums[left+1]){
                        left++;
                    }
                    while (left<right && nums[right] == nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }

            }
        }
        return  res;
    }

}
